package com.heima.leetcode.datastructure.binarysearchtree;

/**
 * <strong>删除二叉搜索树节点 450</strong>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/11 11:11
 */
public class DeleteBSTNode {

    /**
     * 删除二叉搜索树中的节点
     *
     * @param root 当前二叉搜索树的根节点
     * @param key  key
     * @return 删除后二叉树的根节点
     */
    public static TreeNode deleteNode1(TreeNode root, int key) {
        TreeNode curr = root;
        TreeNode parent = null;
        while (curr != null) {
            if (key < curr.val) {
                parent = curr;
                curr = curr.left;
            } else if (curr.val < key) {
                parent = curr;
                curr = curr.right;
            } else {
                break;
            }
        }
        if (curr == null) {
            return root;
        }
        if (curr.left == null) { // 让左子树为null和左子树右子树都为null走这一条，都为null不能走两次
            if (parent == null) {
                root = curr.right;
            }
            shift(parent, curr, curr.right);
        } else if (curr.right == null) {  // 让右子树为null走这一条
            if (parent == null) {
                root = curr.left;
            }
            shift(parent, curr, curr.left);
        }
        if (curr.left != null && curr.right != null) {
            TreeNode successor = curr.right;
            TreeNode sParent = null;
            while (successor.left != null) {
                sParent = successor;
                successor = successor.left;
            }
            if (curr.right == successor) {
                if (parent == null) {
                    root = successor;
                }
                shift(parent, curr, successor);
                successor.left = curr.left;
            } else {
                shift(sParent, successor, successor.right);
                if (parent == null) {
                    root = successor;
                }
                shift(parent, curr, successor);
                successor.left = curr.left;
                successor.right = curr.right;
            }
        }
        return root;
    }

    /**
     * 删除二叉搜索树中的节点
     * @param root 当前子树的根节点
     * @param key key
     * @return 返回的是当前子树删除指定节点重构后的根节点
     */
    public static TreeNode deleteNode2(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            root.left = deleteNode2(root.left, key); // 让当前树的左子树删除指定节点并返回删除过后的左子树的根节点
        } else if (root.val < key) {
            root.right = deleteNode2(root.right, key); // 让当前树的右子树删除指定节点并返回删除节点后的右子树的根节点
        } else {
            // 到这里说明当前树的根节点就是要删除的节点

            // 左子树为null或者左子树和右子树都为null
            if (root.left == null) {
                root = root.right;
                return root;
            }
            // 右子树为null，左子树不能为null
            else if (root.right == null) {
                root = root.left;
                return root;
            }
            // 左子树右子树都不为null
            else {
                // 找后继节点
                TreeNode successor = root.right;
                TreeNode sParent = null;
                while (successor.left != null) {
                    sParent = successor;
                    successor = successor.left;
                }
                // 后继节点是不是与被删除节点：当前树的根节点root相邻
                if (root.right == successor) {
                    successor.left = root.left; // successor不可能有左子树
                    root = successor;
                    return root;
                }
                // 后继节点与被删除节点不相邻
                else {
                    // 则要把后继节点从以后继节点为根节点的树S中删除并把删除后继节点后改变过后的树S接到后继节点的父节点的左边（后继节点可定是其父节点的左子节点）
                    sParent.left = deleteNode2(successor, successor.val);
                    // 然后把后继节点替换掉删除节点root
                    successor.left = root.left;
                    successor.right = root.right;
                    root = successor;
                    return root;
                }
            }
        }
        return root;
    }

    /**
     * 删除二叉搜索树中的节点O(H)，H是树高，精简版本
     * @param root 当前子树的根节点
     * @param key key
     * @return 返回的是当前子树删除指定节点重构后的根节点
     */
    public static TreeNode deleteNode3(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            root.left = deleteNode3(root.left, key); // 让当前树的左子树删除指定节点并返回删除过后的左子树的根节点
        } else if (root.val < key) {
            root.right = deleteNode3(root.right, key); // 让当前树的右子树删除指定节点并返回删除节点后的右子树的根节点
        } else {
            // 到这里说明当前树的根节点就是要删除的节点

            // 左子树为null或者左子树和右子树都为null
            if (root.left == null) {
                return root.right;
            }
            // 右子树为null，左子树不能为null
            else if (root.right == null) {
                return root.left;
            }
            // 左子树右子树都不为null
            else {
                // 找后继节点
                TreeNode successor = root.right;
                while (successor.left != null) {
                    successor = successor.left;
                }
                // 将后继节点从右子树中删除并返回重构后的右子树的根节点并接到当前树根节点后继节点的右子树
                // 让当前树的根节点也就是删除节点更换为后继节点。
                // 原来被删除节点的左子树接到后继节点的左子树
                root.right = deleteNode3(root.right, successor.val);
                root.val = successor.val; // 修改值替代去修改指针
                return root;
            }
        }
        return root;
    }

    /**
     * 托孤方法
     *
     * @param parent  删除节点的父节点
     * @param deleted 删除节点
     * @param child   需要托孤的节点
     */
    private static void shift(TreeNode parent, TreeNode deleted, TreeNode child) {
        if (parent == null) {
            return;
        }
        if (parent.left == deleted) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }
}
